home *** CD-ROM | disk | FTP | other *** search
/ STraTOS 1997 April & May / STraTOS 1 - 1997 April & May.iso / CD01 / INTERNET / SITES / LITTLE / P3SRC.ZIP / ATARI / LBUFFER.C < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-18  |  31.4 KB  |  1,403 lines
  1. /****************************************************************************
  2. *                   lbuffer.c
  3. *
  4. *  This module implements functions that implement the light buffer.
  5. *
  6. *  This module was written by Dieter Bayer [DB].
  7. *
  8. *  from Persistence of Vision(tm) Ray Tracer
  9. *  Copyright 1996 Persistence of Vision Team
  10. *---------------------------------------------------------------------------
  11. *  NOTICE: This source code file is provided so that users may experiment
  12. *  with enhancements to POV-Ray and to port the software to platforms other
  13. *  than those supported by the POV-Ray Team.  There are strict rules under
  14. *  which you are permitted to use this file.  The rules are in the file
  15. *  named POVLEGAL.DOC which should be distributed with this file. If
  16. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  17. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  18. *  Forum.  The latest version of POV-Ray may be found there as well.
  19. *
  20. * This program is based on the popular DKB raytracer version 2.12.
  21. * DKBTrace was originally written by David K. Buck.
  22. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  23. *
  24. *****************************************************************************/
  25.  
  26. /****************************************************************************
  27. *
  28. *  Explanation:
  29. *
  30. *    -
  31. *
  32. *  ---
  33. *
  34. *  Mar 1994 : Creation.
  35. *
  36. *****************************************************************************/
  37.  
  38. #include "frame.h"
  39. #include "vector.h"
  40. #include "povproto.h"
  41. #include "point.h"
  42. #include "povray.h"
  43. #include "bbox.h"
  44. #include "lbuffer.h"
  45. #include "objects.h"
  46. #include "triangle.h"
  47. #include "vlbuffer.h"
  48.  
  49.  
  50.  
  51. /*****************************************************************************
  52. * Local preprocessor defines
  53. ******************************************************************************/
  54.  
  55.  
  56.  
  57. /*****************************************************************************
  58. * Local typedefs
  59. ******************************************************************************/
  60.  
  61.  
  62.  
  63. /*****************************************************************************
  64. * Local variabls
  65. ******************************************************************************/
  66.  
  67. /* Planes for 3d-clipping. */
  68.  
  69. static VECTOR VIEW_VX1 = {-0.7071067812, 0.0, -0.7071067812};
  70. static VECTOR VIEW_VX2 = { 0.7071067812, 0.0, -0.7071067812};
  71. static VECTOR VIEW_VY1 = {0.0, -0.7071067812, -0.7071067812};
  72. static VECTOR VIEW_VY2 = {0.0,  0.7071067812, -0.7071067812};
  73. static DBL VIEW_DX1 = 0.0;
  74. static DBL VIEW_DX2 = 0.0;
  75. static DBL VIEW_DY1 = 0.0;
  76. static DBL VIEW_DY2 = 0.0;
  77.  
  78.  
  79.  
  80. /*****************************************************************************
  81. * Static functions
  82. ******************************************************************************/
  83.  
  84. static void calc_points PARAMS((int Axis, OBJECT *Object, int *Number, VECTOR *Points, VECTOR Origin));
  85.  
  86. static int bbox_invisible PARAMS((int Axis, BBOX *BBox, VECTOR Origin));
  87.  
  88. static void project_rectangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible));
  89. static void project_triangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible));
  90. static void project_bbox PARAMS((PROJECT *Project, VECTOR *P, int *visible));
  91. static void project_object PARAMS((PROJECT *Project, OBJECT *Object, int Axis, VECTOR Origin));
  92.  
  93. static void project_bounding_slab PARAMS((int Axis, VECTOR Origin,
  94.   PROJECT *Project, PROJECT_TREE_NODE **Entry, BBOX_TREE *Node));
  95.  
  96.  
  97.  
  98. /*****************************************************************************
  99. *
  100. * FUNCTION
  101. *
  102. *   calc_points
  103. *
  104. * INPUT
  105. *
  106. *   Axis   - Axis along the objects will be projected
  107. *   Object - Object
  108. *   Number - Number of points to project
  109. *   Points - Points to project
  110. *   Origin - Origin of current light source
  111. *   
  112. * OUTPUT
  113. *
  114. *   Number, Points
  115. *   
  116. * RETURNS
  117. *   
  118. * AUTHOR
  119. *
  120. *   Dieter Bayer
  121. *   
  122. * DESCRIPTION
  123. *
  124. *   Calculate the points to project depending on the object type,
  125. *   the light source position and the axis. Note that only three
  126. *   points are used for triangles and eight for all other objects.
  127. *
  128. * CHANGES
  129. *
  130. *   May 1994 : Creation.
  131. *
  132. ******************************************************************************/
  133.  
  134. static void calc_points(Axis, Object, Number, Points, Origin)
  135. int Axis;
  136. OBJECT *Object;
  137. int *Number;
  138. VECTOR *Points, Origin;
  139. {
  140.   register int i;
  141.   DBL Direction;
  142.   VECTOR P[8];
  143.  
  144.   /* Get points depending on object's type */
  145.  
  146.   if ((Object->Methods == &Triangle_Methods) ||
  147.       (Object->Methods == &Smooth_Triangle_Methods))
  148.   {
  149.     if (Object->Methods == &Triangle_Methods)
  150.     {
  151.       *Number = 3;
  152.  
  153.       Assign_Vector(P[0], ((TRIANGLE *)Object)->P1);
  154.       Assign_Vector(P[1], ((TRIANGLE *)Object)->P2);
  155.       Assign_Vector(P[2], ((TRIANGLE *)Object)->P3);
  156.     }
  157.  
  158.     if (Object->Methods == &Smooth_Triangle_Methods)
  159.     {
  160.       *Number = 3;
  161.  
  162.       Assign_Vector(P[0], ((SMOOTH_TRIANGLE *)Object)->P1);
  163.       Assign_Vector(P[1], ((SMOOTH_TRIANGLE *)Object)->P2);
  164.       Assign_Vector(P[2], ((SMOOTH_TRIANGLE *)Object)->P3);
  165.     }
  166.   }
  167.   else
  168.   {
  169.     *Number = 8;
  170.  
  171.     for (i = 0; i < *Number; i++)
  172.     {
  173.       Assign_BBox_Vect(P[i], Object->BBox.Lower_Left);
  174.  
  175.       P[i][X] += ((i & 1) ? Object->BBox.Lengths[X] : 0.0);
  176.       P[i][Y] += ((i & 2) ? Object->BBox.Lengths[Y] : 0.0);
  177.       P[i][Z] += ((i & 4) ? Object->BBox.Lengths[Z] : 0.0);
  178.     }
  179.   }
  180.  
  181.   /* The points' coordinates need to be relative to the light source */
  182.  
  183.   for (i = 0; i < *Number; i++)
  184.   {
  185.     P[i][X] -= Origin[X];
  186.     P[i][Y] -= Origin[Y];
  187.     P[i][Z] -= Origin[Z];
  188.   }
  189.  
  190.   /* Switch axes so that the specified axis becomes the +Z-axis */
  191.  
  192.   if ((Axis == XaxisP) || (Axis == YaxisP) || (Axis == ZaxisP))
  193.   {
  194.     Direction = 1.0;
  195.   }
  196.   else
  197.   {
  198.     Direction = -1.0;
  199.   }
  200.  
  201.   /* Modify points so that the new z direction is the projection axis */
  202.  
  203.   switch (Axis)
  204.   {
  205.     case XaxisP :
  206.     case XaxisM :
  207.  
  208.       for (i = 0; i < *Number; i++)
  209.       {
  210.         Points[i][X] = P[i][Y];
  211.         Points[i][Y] = P[i][Z];
  212.         Points[i][Z] = P[i][X] * Direction;
  213.       }
  214.  
  215.       break;
  216.  
  217.     case YaxisP :
  218.     case YaxisM :
  219.  
  220.       for (i = 0; i < *Number; i++)
  221.       {
  222.         Points[i][X] = P[i][X];
  223.         Points[i][Y] = P[i][Z];
  224.         Points[i][Z] = P[i][Y] * Direction;
  225.       }
  226.  
  227.       break;
  228.  
  229.     case ZaxisP :
  230.     case ZaxisM :
  231.  
  232.       for (i = 0; i < *Number; i++)
  233.       {
  234.         Points[i][X] = P[i][X];
  235.         Points[i][Y] = P[i][Y];
  236.         Points[i][Z] = P[i][Z] * Direction;
  237.       }
  238.  
  239.       break;
  240.  
  241.     default : Error("Illegal axis in module calc_points() in lbuffer.c.\n");
  242.   }
  243. }
  244.  
  245.  
  246.  
  247. /*****************************************************************************
  248. *
  249. * FUNCTION
  250. *
  251. *   bbox_invisible
  252. *
  253. * INPUT
  254. *
  255. *   Axis   - Axis along the objects will be projected
  256. *   BBox   - Bounding box to test
  257. *   Origin - Origin of current light source
  258. *
  259. * OUTPUT
  260. *
  261. * RETURNS
  262. *
  263. *   int - Flag if bounding box is totally invisble
  264. *
  265. * AUTHOR
  266. *
  267. *   Dieter Bayer
  268. *
  269. * DESCRIPTION
  270. *
  271. *   Do a quick test if a bounding box is totally invisble from the
  272. *   current light source in the specified axis direction.
  273. *
  274. * CHANGES
  275. *
  276. *   May 1994 : Creation.
  277. *
  278. ******************************************************************************/
  279.  
  280. static int bbox_invisible(Axis, BBox, Origin)
  281. int Axis;
  282. BBOX *BBox;
  283. VECTOR Origin;
  284. {
  285.   DBL x1, y1, z1, x2, y2, z2, x, y, z;
  286.  
  287.   switch (Axis)
  288.   {
  289.     case XaxisP :
  290.  
  291.       /* Bounding box behind light source? */
  292.  
  293.       if ((x = BBox->Lower_Left[X] + BBox->Lengths[X] - Origin[X]) <= 0.0)
  294.       {
  295.         return(TRUE);
  296.       }
  297.  
  298.       /* Bounding box on the right/left side? */
  299.  
  300.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  301.       y2 = y1 + BBox->Lengths[Y];
  302.  
  303.       if (((y1 > 0.0) && (y1 > x)) || ((y2 < 0.0) && (-y2 > x)))
  304.       {
  305.         return(TRUE);
  306.       }
  307.  
  308.       /* Bounding box on the bottom/top side? */
  309.  
  310.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  311.       z2 = z1 + BBox->Lengths[Z];
  312.  
  313.       if (((z1 > 0.0) && (z1 > x)) || ((z2 < 0.0) && (-z2 > x)))
  314.       {
  315.         return(TRUE);
  316.       }
  317.  
  318.       break;
  319.  
  320.     case XaxisM :
  321.  
  322.       /* Bounding box behind light source? */
  323.  
  324.       if ((x = BBox->Lower_Left[X] - Origin[X]) >= 0.0)
  325.       {
  326.         return(TRUE);
  327.       }
  328.  
  329.       /* Bounding box on the right/left side? */
  330.  
  331.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  332.       y2 = y1 + BBox->Lengths[Y];
  333.  
  334.       if (((y1 > 0.0) && (y1 > -x)) || ((y2 < 0.0) && (y2 < x)))
  335.       {
  336.         return(TRUE);
  337.       }
  338.  
  339.       /* Bounding box on the bottom/top side? */
  340.  
  341.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  342.       z2 = z1 + BBox->Lengths[Z];
  343.  
  344.       if (((z1 > 0.0) && (z1 > -x)) || ((z2 < 0.0) && (z2 < x)))
  345.       {
  346.         return(TRUE);
  347.       }
  348.  
  349.       break;
  350.  
  351.     case YaxisP :
  352.  
  353.       /* Bounding box behind light source? */
  354.  
  355.       if ((y = BBox->Lower_Left[Y] + BBox->Lengths[Y] - Origin[Y]) <= 0.0)
  356.       {
  357.         return(TRUE);
  358.       }
  359.  
  360.       /* Bounding box on the right/left side? */
  361.  
  362.       x1 = BBox->Lower_Left[X] - Origin[X];
  363.       x2 = x1 + BBox->Lengths[X];
  364.  
  365.       if (((x1 > 0.0) && (x1 > y)) || ((x2 < 0.0) && (-x2 > y)))
  366.       {
  367.         return(TRUE);
  368.       }
  369.  
  370.       /* Bounding box on the bottom/top side? */
  371.  
  372.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  373.       z2 = z1 + BBox->Lengths[Z];
  374.  
  375.       if (((z1 > 0.0) && (z1 > y)) || ((z2 < 0.0) && (-z2 > y)))
  376.       {
  377.         return(TRUE);
  378.       }
  379.  
  380.       break;
  381.  
  382.     case YaxisM :
  383.  
  384.       /* Bounding box behind light source? */
  385.  
  386.       if ((y = BBox->Lower_Left[Y] - Origin[Y]) >= 0.0)
  387.       {
  388.         return(TRUE);
  389.       }
  390.  
  391.       /* Bounding box on the right/left side? */
  392.  
  393.       x1 = BBox->Lower_Left[X] - Origin[X];
  394.       x2 = x1 + BBox->Lengths[X];
  395.  
  396.       if (((x1 > 0.0) && (x1 > -y)) || ((x2 < 0.0) && (x2 < y)))
  397.       {
  398.         return(TRUE);
  399.       }
  400.  
  401.       /* Bounding box on the bottom/top side? */
  402.  
  403.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  404.       z2 = z1 + BBox->Lengths[Z];
  405.  
  406.       if (((z1 > 0.0) && (z1 > -y)) || ((z2 < 0.0) && (z2 < y)))
  407.       {
  408.         return(TRUE);
  409.       }
  410.  
  411.       break;
  412.  
  413.     case ZaxisP :
  414.  
  415.       /* Bounding box behind light source? */
  416.  
  417.       if ((z = BBox->Lower_Left[Z] + BBox->Lengths[Z] - Origin[Z]) <= 0.0)
  418.       {
  419.         return(TRUE);
  420.       }
  421.  
  422.       /* Bounding box on the right/left side? */
  423.  
  424.       x1 = BBox->Lower_Left[X] - Origin[X];
  425.       x2 = x1 + BBox->Lengths[X];
  426.  
  427.       if (((x1 > 0.0) && (x1 > z)) || ((x2 < 0.0) && (-x2 > z)))
  428.       {
  429.         return(TRUE);
  430.       }
  431.  
  432.       /* Bounding box on the bottom/top side? */
  433.  
  434.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  435.       y2 = y1 + BBox->Lengths[Y];
  436.  
  437.       if (((y1 > 0.0) && (y1 > z)) || ((y2 < 0.0) && (-y2 > z)))
  438.       {
  439.         return(TRUE);
  440.       }
  441.  
  442.       break;
  443.  
  444.     case ZaxisM :
  445.  
  446.       /* Bounding box behind light source? */
  447.  
  448.       if ((z = BBox->Lower_Left[Z] - Origin[Z]) >= 0.0)
  449.       {
  450.         return(TRUE);
  451.       }
  452.  
  453.       /* Bounding box on the right/left side? */
  454.  
  455.       x1 = BBox->Lower_Left[X] - Origin[X];
  456.       x2 = x1 + BBox->Lengths[X];
  457.  
  458.       if (((x1 > 0.0) && (x1 > -z)) || ((x2 < 0.0) && (x2 < z)))
  459.       {
  460.         return(TRUE);
  461.       }
  462.  
  463.       /* Bounding box on the bottom/top side? */
  464.  
  465.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  466.       y2 = y1 + BBox->Lengths[Y];
  467.  
  468.       if (((y1 > 0.0) && (y1 > -z)) || ((y2 < 0.0) && (y2 < z)))
  469.       {
  470.         return(TRUE);
  471.       }
  472.  
  473.       break;
  474.  
  475.     default :
  476.  
  477.       Error("Illegal axis in bbox_invisible() in lbuffer.c.\n");
  478.   }
  479.  
  480.   return(FALSE);
  481. }
  482.  
  483.  
  484.  
  485. /*****************************************************************************
  486. *
  487. * FUNCTION
  488. *
  489. *   project_rectangle
  490. *
  491. * INPUT
  492. *
  493. *   Project        - Rectangle's projection
  494. *   P1, P2, P3, P4 - Rectangle's edges
  495. *   visible        - Flag if rectangle is visible
  496. *
  497. * OUTPUT
  498. *
  499. *   Project, visible
  500. *   
  501. * RETURNS
  502. *   
  503. * AUTHOR
  504. *
  505. *   Dieter Bayer
  506. *   
  507. * DESCRIPTION
  508. *
  509. *   Project a rectangle onto a light source.
  510. *
  511. * CHANGES
  512. *
  513. *   May 1994 : Creation.
  514. *
  515. ******************************************************************************/
  516.  
  517. static void project_rectangle(Project, P1, P2, P3, P4, visible)
  518. PROJECT *Project;
  519. VECTOR P1, P2, P3, P4;
  520. int *visible;
  521. {
  522.   VECTOR Points[MAX_CLIP_POINTS];
  523.   int i, number;
  524.   int x, y;
  525.   DBL rdiv;
  526.   
  527.   Assign_Vector(Points[0], P1);
  528.   Assign_Vector(Points[1], P2);
  529.   Assign_Vector(Points[2], P3);
  530.   Assign_Vector(Points[3], P4);
  531.  
  532.   number = 4;
  533.  
  534.   Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
  535.                                 VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
  536.  
  537.   if (number)
  538.   {
  539.     for (i = 0; i < number; i++)
  540.     {
  541.       if (Points[i][Z] < EPSILON)
  542.       {
  543.         Points[i][X] = Points[i][Y] = 0.0;
  544.       }
  545.       else
  546.       {
  547.  
  548.         rdiv = (1.0 / Points[i][Z]);
  549.         Points[i][X] *= rdiv;
  550.         Points[i][Y] *= rdiv;
  551. /*
  552.         Points[i][X] /= Points[i][Z];
  553.         Points[i][Y] /= Points[i][Z];
  554. */
  555.  
  556.         if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
  557.         if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
  558.       }
  559.  
  560.       x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
  561.       y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
  562.  
  563.       if (x < Project->x1) Project->x1 = x;
  564.       if (x > Project->x2) Project->x2 = x;
  565.       if (y < Project->y1) Project->y1 = y;
  566.       if (y > Project->y2) Project->y2 = y;
  567.     }
  568.  
  569.     *visible = TRUE;
  570.   }
  571. }
  572.  
  573.  
  574.  
  575.  
  576. /*****************************************************************************
  577. *
  578. * FUNCTION
  579. *
  580. *   project_triangle
  581. *
  582. * INPUT
  583. *
  584. *   Project    - Triangle's projection
  585. *   P1, P2, P3 - Triangles's edges
  586. *   visible    - Flag if triangle is visible
  587. *   
  588. * OUTPUT
  589. *
  590. *   Project, visible
  591. *   
  592. * RETURNS
  593. *   
  594. * AUTHOR
  595. *
  596. *   Dieter Bayer
  597. *   
  598. * DESCRIPTION
  599. *
  600. *   Project a triangle onto a light source.
  601. *
  602. * CHANGES
  603. *
  604. *   May 1994 : Creation.
  605. *
  606. ******************************************************************************/
  607.  
  608. static void project_triangle(Project, P1, P2, P3, visible)
  609. PROJECT *Project;
  610. VECTOR P1, P2, P3;
  611. int *visible;
  612. {
  613.   VECTOR Points[MAX_CLIP_POINTS];
  614.   int i, number;
  615.   int x, y, clip;
  616.   DBL rdiv;
  617.   
  618.   clip = TRUE;
  619.  
  620.   /* Check if all points lie "in front" of the light source. */
  621.  
  622.   if ((P1[Z] > 0.0) && (P2[Z] > 0.0) && (P3[Z] > 0.0))
  623.   {
  624.     /* Check if all points lie inside the "viewing pyramid". */
  625.  
  626.     if ((fabs(P1[X]) <= P1[Z]) && (fabs(P2[X]) <= P2[Z]) && (fabs(P3[X]) <= P3[Z]) &&
  627.         (fabs(P1[Y]) <= P1[Z]) && (fabs(P2[Y]) <= P2[Z]) && (fabs(P3[Y]) <= P3[Z]))
  628.     {
  629.       /* No clipping is needed. Just project the points. */
  630.  
  631.       clip = FALSE;
  632.     }
  633.     else
  634.     {
  635.       /* Check if all points lie on the "right side". */
  636.  
  637.       if ((P1[X] > 0.0) && (P1[X] > P1[Z]) &&
  638.           (P2[X] > 0.0) && (P2[X] > P2[Z]) &&
  639.           (P3[X] > 0.0) && (P3[X] > P3[Z]))
  640.       {
  641.         return;
  642.       }
  643.  
  644.       /* Check if all points lie on the "left side". */
  645.  
  646.       if ((P1[X] < 0.0) && (-P1[X] > P1[Z]) &&
  647.           (P2[X] < 0.0) && (-P2[X] > P2[Z]) &&
  648.           (P3[X] < 0.0) && (-P3[X] > P3[Z]))
  649.       {
  650.         return;
  651.       }
  652.  
  653.       /* Check if all points lie above the "top side". */
  654.  
  655.       if ((P1[Y] > 0.0) && (P1[Y] > P1[Z]) &&
  656.           (P2[Y] > 0.0) && (P2[Y] > P2[Z]) &&
  657.           (P3[Y] > 0.0) && (P3[Y] > P3[Z]))
  658.       {
  659.         return;
  660.       }
  661.  
  662.       /* Check if all points lie below the "bottom side". */
  663.  
  664.       if ((P1[Y] < 0.0) && (-P1[Y] > P1[Z]) &&
  665.           (P2[Y] < 0.0) && (-P2[Y] > P2[Z]) &&
  666.           (P3[Y] < 0.0) && (-P3[Y] > P3[Z]))
  667.       {
  668.         return;
  669.       }
  670.     }
  671.   }
  672.  
  673.   Assign_Vector(Points[0], P1);
  674.   Assign_Vector(Points[1], P2);
  675.   Assign_Vector(Points[2], P3);
  676.  
  677.   number = 3;
  678.  
  679.   if (clip)
  680.   {
  681.     Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
  682.                                   VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
  683.   }
  684.  
  685.   if (number)
  686.   {
  687.     for (i = 0; i < number; i++)
  688.     {
  689.       if (fabs(Points[i][Z]) < EPSILON)
  690.       {
  691.         Points[i][X] = Points[i][Y] = 0.0;
  692.       }
  693.       else
  694.       {
  695.  
  696.         rdiv = (1.0 / Points[i][Z]);
  697.         Points[i][X] *= rdiv;
  698.         Points[i][Y] *= rdiv;
  699. /*
  700.         Points[i][X] /= Points[i][Z];
  701.         Points[i][Y] /= Points[i][Z];
  702. */
  703.  
  704.         if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
  705.         if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
  706.       }
  707.  
  708.       x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
  709.       y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
  710.  
  711.       if (x < Project->x1) Project->x1 = x;
  712.       if (x > Project->x2) Project->x2 = x;
  713.       if (y < Project->y1) Project->y1 = y;
  714.       if (y > Project->y2) Project->y2 = y;
  715.     }
  716.  
  717.     *visible = TRUE;
  718.   }
  719. }
  720.  
  721.  
  722.  
  723.  
  724. /*****************************************************************************
  725. *
  726. * FUNCTION
  727. *
  728. *   Project_BBox
  729. *
  730. * INPUT
  731. *
  732. *   Project - Box's projection
  733. *   P       - Box's edges
  734. *   visible - Flag if box is visible
  735. *   
  736. * OUTPUT
  737. *
  738. *   Project, visible
  739. *   
  740. * RETURNS
  741. *   
  742. * AUTHOR
  743. *
  744. *   Dieter Bayer
  745. *   
  746. * DESCRIPTION
  747. *
  748. *   Project an axis-aligned box onto a light source.
  749. *
  750. * CHANGES
  751. *
  752. *   May 1994 : Creation.
  753. *
  754. ******************************************************************************/
  755.  
  756. static void project_bbox(Project, P, visible)
  757. PROJECT *Project;
  758. VECTOR *P;
  759. int *visible;
  760. {
  761.   int i, x, y;
  762.   DBL rdiv;
  763.  
  764.   /* Check if all points lie "in front" of the light source. */
  765.  
  766.   if ((P[0][Z] > 0.0) && (P[1][Z] > 0.0) && (P[2][Z] > 0.0) && (P[3][Z] > 0.0) &&
  767.       (P[4][Z] > 0.0) && (P[5][Z] > 0.0) && (P[6][Z] > 0.0) && (P[7][Z] > 0.0))
  768.   {
  769.     /* Check if all points lie inside the "viewing pyramid". */
  770.  
  771.     if ((fabs(P[0][X]) <= P[0][Z]) && (fabs(P[1][X]) <= P[1][Z]) &&
  772.         (fabs(P[2][X]) <= P[2][Z]) && (fabs(P[3][X]) <= P[3][Z]) &&
  773.         (fabs(P[4][X]) <= P[4][Z]) && (fabs(P[5][X]) <= P[5][Z]) &&
  774.         (fabs(P[6][X]) <= P[6][Z]) && (fabs(P[7][X]) <= P[7][Z]) &&
  775.         (fabs(P[0][Y]) <= P[0][Z]) && (fabs(P[1][Y]) <= P[1][Z]) &&
  776.         (fabs(P[2][Y]) <= P[2][Z]) && (fabs(P[3][Y]) <= P[3][Z]) &&
  777.         (fabs(P[4][Y]) <= P[4][Z]) && (fabs(P[5][Y]) <= P[5][Z]) &&
  778.         (fabs(P[6][Y]) <= P[6][Z]) && (fabs(P[7][Y]) <= P[7][Z]))
  779.     {
  780.       /* No clipping is needed. Just project the points. */
  781.  
  782.       for (i = 0; i < 8; i++)
  783.       {
  784.         if (P[i][Z] < EPSILON)
  785.         {
  786.           P[i][X] = P[i][Y] = 0.0;
  787.         }
  788.         else
  789.         {
  790.  
  791.           rdiv = (1.0 / P[i][Z]);
  792.           P[i][X] *= rdiv;
  793.           P[i][Y] *= rdiv;
  794. /*
  795.           P[i][X] /= P[i][Z];
  796.           P[i][Y] /= P[i][Z];
  797. */
  798.  
  799.           if (fabs(P[i][X]) < EPSILON) P[i][X] = 0.0;
  800.           if (fabs(P[i][Y]) < EPSILON) P[i][Y] = 0.0;
  801.         }
  802.  
  803.         x = (int)(MAX_BUFFER_ENTRY * P[i][X]);
  804.         y = (int)(MAX_BUFFER_ENTRY * P[i][Y]);
  805.  
  806.         if (x < Project->x1) Project->x1 = x;
  807.         if (x > Project->x2) Project->x2 = x;
  808.         if (y < Project->y1) Project->y1 = y;
  809.         if (y > Project->y2) Project->y2 = y;
  810.       }
  811.  
  812.       *visible = TRUE;
  813.  
  814.       return;
  815.     }
  816.     else
  817.     {
  818.       /* Check if all points lie on the "right side". */
  819.  
  820.       for (i = 0; i < 8; i++)
  821.       {
  822.         if ((P[i][X] < 0.0) || (P[i][X] <= P[i][Z])) break;
  823.       }
  824.  
  825.       if (i == 8) return;
  826.  
  827.       /* Check if all points lie on the "left side". */
  828.  
  829.       for (i = 0; i < 8; i++)
  830.       {
  831.         if ((P[i][X] > 0.0) || (-P[i][X] <= P[i][Z])) break;
  832.       }
  833.  
  834.       if (i == 8) return;
  835.  
  836.       /* Check if all points lie above the "top side". */
  837.  
  838.       for (i = 0; i < 8; i++)
  839.       {
  840.         if ((P[i][Y] < 0.0) || (P[i][Y] <= P[i][Z])) break;
  841.       }
  842.  
  843.       if (i == 8) return;
  844.  
  845.       /* Check if all points lie below the "bottom side". */
  846.  
  847.       for (i = 0; i < 8; i++)
  848.       {
  849.         if ((P[i][Y] > 0.0) || (-P[i][Y] <= P[i][Z])) break;
  850.       }
  851.  
  852.       if (i == 8) return;
  853.     }
  854.   }
  855.  
  856.   project_rectangle(Project, P[0], P[1], P[3], P[2], visible);
  857.   project_rectangle(Project, P[4], P[5], P[7], P[6], visible);
  858.   project_rectangle(Project, P[0], P[1], P[5], P[4], visible);
  859.   project_rectangle(Project, P[2], P[3], P[7], P[6], visible);
  860.   project_rectangle(Project, P[1], P[3], P[7], P[5], visible);
  861.   project_rectangle(Project, P[0], P[2], P[6], P[4], visible);
  862. }
  863.  
  864.  
  865.  
  866. /*****************************************************************************
  867. *
  868. * FUNCTION
  869. *
  870. *   project_object
  871. *
  872. * INPUT
  873. *
  874. *   Object   - Object to project
  875. *   Project  - Projection
  876. *   
  877. * OUTPUT
  878. *
  879. *   Project
  880. *
  881. * RETURNS
  882. *   
  883. * AUTHOR
  884. *
  885. *   Dieter Bayer
  886. *   
  887. * DESCRIPTION
  888. *
  889. *   Get the projection of a single object onto a light source.
  890. *
  891. * CHANGES
  892. *
  893. *   May 1994 : Creation.
  894. *
  895. ******************************************************************************/
  896.  
  897. static void project_object(Project, Object, Axis, Origin)
  898. PROJECT *Project;
  899. OBJECT *Object;
  900. int Axis;
  901. VECTOR Origin;
  902. {
  903.   int visible, Number;
  904.   VECTOR Points[8];
  905.  
  906.   /* Do not project infinite objects (always visible!) */
  907.  
  908.   if (Test_Flag(Object, INFINITE_FLAG))
  909.   {
  910.     Project->x1 = Project->y1 = MIN_BUFFER_ENTRY;
  911.     Project->x2 = Project->y2 = MAX_BUFFER_ENTRY;
  912.  
  913.     return;
  914.   }
  915.  
  916.   /* Get points to project */
  917.  
  918.   calc_points(Axis, Object, &Number, Points, Origin);
  919.  
  920.   visible = FALSE;
  921.  
  922.   Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
  923.   Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
  924.  
  925.   if (Number == 3)
  926.   {
  927.     project_triangle(Project, Points[0], Points[1], Points[2], &visible);
  928.   }
  929.   else
  930.   {
  931.     project_bbox(Project, Points, &visible);
  932.   }
  933.  
  934.   if (!visible)
  935.   {
  936.     /* Object is invisible */
  937.  
  938.     Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
  939.     Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
  940.   }
  941.   else
  942.   {
  943.     /* We don't want to miss something */
  944.  
  945.     Project->x1 -= 2;
  946.     Project->x2 += 2;
  947.     Project->y1 -= 2;
  948.     Project->y2 += 2;
  949.   }
  950. }
  951.  
  952.  
  953.  
  954. /*****************************************************************************
  955. *
  956. * FUNCTION
  957. *
  958. *   project_bounding_slab
  959. *
  960. * INPUT
  961. *
  962. *   Axis     - Axis along the objects will be projected
  963. *   Origin   - Origin of current light source
  964. *   Project  - Projection
  965. *   Tree     - Current node/leaf
  966. *   Object   - Node/leaf in bounding slab hierarchy
  967. *   
  968. * OUTPUT
  969. *
  970. *   Project, Tree
  971. *   
  972. * RETURNS
  973. *   
  974. * AUTHOR
  975. *
  976. *   Dieter Bayer
  977. *   
  978. * DESCRIPTION
  979. *
  980. *   Project the bounding slab hierarchy onto a light source and thus create
  981. *   the light buffer hierarchy for this light source.
  982. *
  983. * CHANGES
  984. *
  985. *   May 1994 : Creation.
  986. *
  987. ******************************************************************************/
  988.  
  989. static void project_bounding_slab(Axis, Origin, Project, Tree, Node)
  990. int Axis;
  991. VECTOR Origin;
  992. PROJECT *Project;
  993. PROJECT_TREE_NODE **Tree;
  994. BBOX_TREE *Node;
  995. {
  996.   short int i;
  997.   PROJECT Temp;
  998.   PROJECT_TREE_LEAF *Leaf;
  999.   PROJECT_TREE_NODE New;
  1000.  
  1001.   COOPERATE_1
  1002.  
  1003.   /* If the node is totally invisible we are ready. */
  1004.  
  1005.   if (bbox_invisible(Axis, &Node->BBox, Origin))
  1006.   {
  1007.     return;
  1008.   }
  1009.  
  1010.   if (Node->Entries)
  1011.   {
  1012.     /* Current object is a bounding object, i.e. a node in the slab tree. */
  1013.  
  1014.     /* First, Init new entry. */
  1015.  
  1016.     New.Entries = 0;
  1017.  
  1018.     New.Node = Node;
  1019.  
  1020.     New.Project.x1 = New.Project.y1 = MAX_BUFFER_ENTRY;
  1021.     New.Project.x2 = New.Project.y2 = MIN_BUFFER_ENTRY;
  1022.  
  1023.     /* Allocate temporary memory for node/leaf entries. */
  1024.  
  1025.     New.Entry = (PROJECT_TREE_NODE **)POV_MALLOC(Node->Entries*sizeof(PROJECT_TREE_NODE *), "temporary tree entry");
  1026.  
  1027.     /* This is no leaf, it's a node. */
  1028.  
  1029.     New.is_leaf = FALSE;
  1030.  
  1031.     /* Second, Get new entry, i.e. project bounding slab's entries. */
  1032.  
  1033.     for (i = 0; i < Node->Entries; i++)
  1034.     {
  1035.       New.Entry[i] = NULL;
  1036.  
  1037.       project_bounding_slab(Axis, Origin, &Temp, &New.Entry[New.Entries], Node->Node[i]);
  1038.  
  1039.       /* Use only visible entries. */
  1040.  
  1041.       if (New.Entry[New.Entries] != NULL)
  1042.       {
  1043.         New.Project.x1 = min(New.Project.x1, Temp.x1);
  1044.         New.Project.x2 = max(New.Project.x2, Temp.x2);
  1045.         New.Project.y1 = min(New.Project.y1, Temp.y1);
  1046.         New.Project.y2 = max(New.Project.y2, Temp.y2);
  1047.  
  1048.         New.Entries++;
  1049.       }
  1050.     }
  1051.  
  1052.     /* If there are any visible entries, we'll use them. */
  1053.  
  1054.     if (New.Entries > 0)
  1055.     {
  1056.       /* If there's only one entry, we won't need a new node. */
  1057.  
  1058.       if (New.Entries == 1)
  1059.       {
  1060.         *Tree    = New.Entry[0];
  1061.         *Project = New.Project;
  1062.       }
  1063.       else
  1064.       {
  1065.         /* Allocate memory for new node in the light tree. */
  1066.  
  1067.         *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_NODE), "light tree node");
  1068.  
  1069.         **Tree = New;
  1070.  
  1071.         /* Allocate memory for node/leaf entries. */
  1072.  
  1073.         (*Tree)->Entry = (PROJECT_TREE_NODE **)POV_MALLOC(New.Entries*sizeof(PROJECT_TREE_NODE *), "light tree node");
  1074.  
  1075.         memcpy((*Tree)->Entry, New.Entry, New.Entries*sizeof(PROJECT_TREE_NODE *));
  1076.  
  1077.         *Project = New.Project;
  1078.       }
  1079.     }
  1080.  
  1081.     /* Get rid of temporary node/leaf entries. */
  1082.  
  1083.     POV_FREE(New.Entry);
  1084.   }
  1085.   else
  1086.   {
  1087.     /* Current object is a normal object, i.e. a leaf in the slab tree. */
  1088.  
  1089.     /* If object doesn't cast shadows we can skip. */
  1090.  
  1091.     if (!Test_Flag((OBJECT *)Node->Node, NO_SHADOW_FLAG))
  1092.     {
  1093.       /* Project object onto light source. */
  1094.  
  1095.       project_object(Project, (OBJECT *)Node->Node, Axis, Origin);
  1096.  
  1097.       /* Is the object visible? */
  1098.  
  1099.       if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2))
  1100.       {
  1101.         /* Allocate memory for new leaf in the light tree. */
  1102.  
  1103.         *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_LEAF), "light tree leaf");
  1104.  
  1105.         /* Init new leaf. */
  1106.  
  1107.         Leaf = (PROJECT_TREE_LEAF *)(*Tree);
  1108.  
  1109.         Leaf->Node = Node;
  1110.  
  1111.         Leaf->Project = *Project;
  1112.  
  1113.         /* Yes, this is a leaf. */
  1114.  
  1115.         Leaf->is_leaf = TRUE;
  1116.       }
  1117.     }
  1118.   }
  1119. }
  1120.  
  1121.  
  1122.  
  1123. /*****************************************************************************
  1124. *
  1125. * FUNCTION
  1126. *
  1127. *   Build_Light_Buffers
  1128. *
  1129. * INPUT
  1130. *   
  1131. * OUTPUT
  1132. *   
  1133. * RETURNS
  1134. *   
  1135. * AUTHOR
  1136. *
  1137. *   Dieter Bayer
  1138. *   
  1139. * DESCRIPTION
  1140. *
  1141. *   Build the light buffers, i.e. the 2d representations of the bounding slab
  1142. *   hierarchy seen from the light sources.
  1143. *
  1144. * CHANGES
  1145. *
  1146. *   May 1994 : Creation.
  1147. *
  1148. ******************************************************************************/
  1149.  
  1150. void Build_Light_Buffers()
  1151. {
  1152.   int Axis;
  1153.   PROJECT Project;
  1154.   LIGHT_SOURCE *Light;
  1155.  
  1156.   if (!(opts.Quality_Flags & Q_SHADOW) || (!opts.Use_Slabs))
  1157.   {
  1158.     opts.Options &= ~USE_LIGHT_BUFFER;
  1159.   }
  1160.  
  1161.   if (opts.Options & USE_LIGHT_BUFFER)
  1162.   {
  1163.     Status_Info("\nCreating light buffers");
  1164.     
  1165.     /* Build the light buffer for all point(!) light sources */
  1166.   
  1167.     for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
  1168.     {
  1169.       if (!Light->Area_Light)
  1170.       {
  1171.         Status_Info(".");
  1172.     
  1173.         /* Project bounding slabs on all six sides */
  1174.   
  1175.         for (Axis = 0; Axis < 6; Axis++)
  1176.         {
  1177.           Light->Light_Buffer[Axis] = NULL;
  1178.   
  1179.           project_bounding_slab(Axis, Light->Center, &Project,
  1180.             &Light->Light_Buffer[Axis], Root_Object);
  1181.         }
  1182.       }
  1183.     }
  1184.   }
  1185. }
  1186.  
  1187.  
  1188.  
  1189. /*****************************************************************************
  1190. *
  1191. * FUNCTION
  1192. *
  1193. *   Destroy_Light_Buffers
  1194. *
  1195. * INPUT
  1196. *   
  1197. * OUTPUT
  1198. *   
  1199. * RETURNS
  1200. *   
  1201. * AUTHOR
  1202. *
  1203. *   Dieter Bayer
  1204. *   
  1205. * DESCRIPTION
  1206. *
  1207. *   Destroy the light buffers.
  1208. *
  1209. * CHANGES
  1210. *
  1211. *   Sep 1994 : Creation.
  1212. *
  1213. ******************************************************************************/
  1214.  
  1215. void Destroy_Light_Buffers()
  1216. {
  1217.   int Axis;
  1218.   LIGHT_SOURCE *Light;
  1219.  
  1220.   if (opts.Options & USE_LIGHT_BUFFER)
  1221.   {
  1222.     for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
  1223.     {
  1224.       if (!Light->Area_Light)
  1225.       {
  1226.         for (Axis = 0; Axis < 6; Axis++)
  1227.         {
  1228.           if (Light->Light_Buffer[Axis] != NULL)
  1229.           {
  1230.             Destroy_Project_Tree(Light->Light_Buffer[Axis]);
  1231.           }
  1232.  
  1233.           Light->Light_Buffer[Axis] = NULL;
  1234.         }
  1235.       }
  1236.     }
  1237.   }
  1238. }
  1239.  
  1240.  
  1241.  
  1242. /*****************************************************************************
  1243. *
  1244. * FUNCTION
  1245. *
  1246. *   Intersect_Light_Tree
  1247. *
  1248. * INPUT
  1249. *
  1250. *   Ray               - Shadow ray
  1251. *   Tree              - Light tree's top-node
  1252. *   x                 - X-coordinate of the shadow ray
  1253. *   y                 - Y-coordinate of the shadow ray
  1254. *   Best_Intersection - Intersection found
  1255. *   Best_Object       - Object found
  1256. *   
  1257. * OUTPUT
  1258. *
  1259. *   Best_Intersection, Best_Object
  1260. *   
  1261. * RETURNS
  1262. *   
  1263. * AUTHOR
  1264. *
  1265. *   Dieter Bayer
  1266. *
  1267. * DESCRIPTION
  1268. *
  1269. *   Intersect a shadow ray with the light tree
  1270. *   (same as for the vista tree but without pruning).
  1271. *
  1272. * CHANGES
  1273. *
  1274. *   May 1994 : Creation.
  1275. *
  1276. ******************************************************************************/
  1277.  
  1278. int Intersect_Light_Tree(Ray, Tree, x, y, Best_Intersection, Best_Object)
  1279. RAY *Ray;
  1280. PROJECT_TREE_NODE *Tree;
  1281. int x, y;
  1282. INTERSECTION *Best_Intersection;
  1283. OBJECT **Best_Object;
  1284. {
  1285.   INTERSECTION New_Intersection;
  1286.   unsigned short i;
  1287.   unsigned size;
  1288.   int Found;
  1289.   RAYINFO rayinfo;
  1290.   DBL key;
  1291.   BBOX_TREE *BBox_Node;
  1292.   PROJECT_TREE_NODE *Node;
  1293.  
  1294.   /* If there's no vista tree then return. */
  1295.  
  1296.   if (Tree == NULL)
  1297.   {
  1298.     return(FALSE);
  1299.   }
  1300.  
  1301.   /* Start with an empty priority queue */
  1302.  
  1303.   VLBuffer_Queue->QSize = 0;
  1304.  
  1305.   Found = FALSE;
  1306.  
  1307. #ifdef BBOX_EXTRA_STATS
  1308.   Increase_Counter(stats[totalQueueResets]);
  1309. #endif
  1310.  
  1311.   /* Traverse the tree. */
  1312.  
  1313.   size = 0;
  1314.  
  1315.   /* Create the direction vectors for this ray */
  1316.  
  1317.   Create_Rayinfo(Ray, &rayinfo);
  1318.  
  1319.   /* Fill the priority queue with all possible candidates */
  1320.  
  1321.   /* Check root */
  1322.  
  1323.   Increase_Counter(stats[LBuffer_Tests]);
  1324.  
  1325.   if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  1326.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  1327.   {
  1328.     Increase_Counter(stats[LBuffer_Tests_Succeeded]);
  1329.  
  1330.     Node_Queue->Queue[size++] = Tree;
  1331.   }
  1332.  
  1333.   /* Loop until queue is empty. */
  1334.  
  1335.   while (size > 0)
  1336.   {
  1337.     Tree = Node_Queue->Queue[--size];
  1338.  
  1339.     if (Tree->is_leaf)
  1340.     {
  1341.       /* Leaf --> test object's bounding box in 3d */
  1342.  
  1343.       Check_And_Enqueue(VLBuffer_Queue,
  1344.         ((PROJECT_TREE_LEAF *)Tree)->Node,
  1345.         &((PROJECT_TREE_LEAF *)Tree)->Node->BBox, &rayinfo);
  1346.     }
  1347.     else
  1348.     {
  1349.       /* Check siblings of the node in 2d */
  1350.  
  1351.       for (i = 0; i < Tree->Entries; i++)
  1352.       {
  1353.         Node = Tree->Entry[i];
  1354.  
  1355.         Increase_Counter(stats[LBuffer_Tests]);
  1356.  
  1357.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  1358.             (y >= Node->Project.y1) && (y <= Node->Project.y2))
  1359.         {
  1360.           Increase_Counter(stats[LBuffer_Tests_Succeeded]);
  1361.  
  1362.           /* Reallocate queues if they're too small. */
  1363.  
  1364.           Reinitialize_VLBuffer_Code();
  1365.  
  1366.           /* Add node to node queue */
  1367.  
  1368.           Node_Queue->Queue[size++] = Node;
  1369.         }
  1370.       }
  1371.     }
  1372.   }
  1373.  
  1374.   /* Now test the candidates in the priority queue */
  1375.  
  1376.   while (VLBuffer_Queue->QSize > 0)
  1377.   {
  1378.     Priority_Queue_Delete(VLBuffer_Queue, &key, &BBox_Node);
  1379.  
  1380.     if (key > Best_Intersection->Depth)
  1381.     {
  1382.       break;
  1383.     }
  1384.  
  1385.     if (Intersection(&New_Intersection, (OBJECT *)BBox_Node->Node, Ray))
  1386.     {
  1387.       if (New_Intersection.Depth < Best_Intersection->Depth)
  1388.       {
  1389.         *Best_Intersection = New_Intersection;
  1390.  
  1391.         *Best_Object = (OBJECT *)BBox_Node->Node;
  1392.  
  1393.         Found = TRUE;
  1394.       }
  1395.     }
  1396.   }
  1397.  
  1398.   return(Found);
  1399. }
  1400.  
  1401.  
  1402.  
  1403.